#include <vector>
#include <iostream>

using namespace std;

// [2, 3, 5, 5, 6, 8, 9]
//     ^i
//     ^j
// if (array[j - 1] > array[j]) {
//   swap(array[j - 1], array[j]);
//   --j;
// }

vector<int> insertionSort(vector<int> array) {
  for (int i = 1; i < array.size(); ++i) {
    int j = i;

    // 比较 j - 1 和 j 位置上 array 的值，
    // 如果 j - 1 位置更大，就交换 j - 1 和 j
  }

  return array;
}

int main(int argc, char const *argv[]) {
  /* code */
  return 0;
}
